//
// Copyright (C) 2024 EA group inc.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//
//
// Created by jeff on 24-6-4.


#include <turbo/container/small_vector.h>
#include <turbo/container/array_ref.h>
#include "ktest/ktest.h"
#include <list>
#include <stdarg.h>

using namespace turbo;

namespace {

    /// A helper class that counts the total number of constructor and
    /// destructor calls.
    class Constructable {
    private:
        static int numConstructorCalls;
        static int numMoveConstructorCalls;
        static int numCopyConstructorCalls;
        static int numDestructorCalls;
        static int numAssignmentCalls;
        static int numMoveAssignmentCalls;
        static int numCopyAssignmentCalls;

        bool constructed;
        int value;

    public:
        Constructable() : constructed(true), value(0) {
            ++numConstructorCalls;
        }

        Constructable(int val) : constructed(true), value(val) {
            ++numConstructorCalls;
        }

        Constructable(const Constructable & src) : constructed(true) {
            value = src.value;
            ++numConstructorCalls;
            ++numCopyConstructorCalls;
        }

        Constructable(Constructable && src) : constructed(true) {
            value = src.value;
            src.value = 0;
            ++numConstructorCalls;
            ++numMoveConstructorCalls;
        }

        ~Constructable() {
            EXPECT_TRUE(constructed);
            ++numDestructorCalls;
            constructed = false;
        }

        Constructable & operator=(const Constructable & src) {
            EXPECT_TRUE(constructed);
            value = src.value;
            ++numAssignmentCalls;
            ++numCopyAssignmentCalls;
            return *this;
        }

        Constructable & operator=(Constructable && src) {
            EXPECT_TRUE(constructed);
            value = src.value;
            src.value = 0;
            ++numAssignmentCalls;
            ++numMoveAssignmentCalls;
            return *this;
        }

        int getValue() const {
            return abs(value);
        }

        static void reset() {
            numConstructorCalls = 0;
            numMoveConstructorCalls = 0;
            numCopyConstructorCalls = 0;
            numDestructorCalls = 0;
            numAssignmentCalls = 0;
            numMoveAssignmentCalls = 0;
            numCopyAssignmentCalls = 0;
        }

        static int getNumConstructorCalls() {
            return numConstructorCalls;
        }

        static int getNumMoveConstructorCalls() {
            return numMoveConstructorCalls;
        }

        static int getNumCopyConstructorCalls() {
            return numCopyConstructorCalls;
        }

        static int getNumDestructorCalls() {
            return numDestructorCalls;
        }

        static int getNumAssignmentCalls() {
            return numAssignmentCalls;
        }

        static int getNumMoveAssignmentCalls() {
            return numMoveAssignmentCalls;
        }

        static int getNumCopyAssignmentCalls() {
            return numCopyAssignmentCalls;
        }

        friend bool operator==(const Constructable &c0, const Constructable &c1) {
            return c0.getValue() == c1.getValue();
        }

        friend bool TURBO_ATTRIBUTE_UNUSED operator!=(const Constructable &c0,
                                                     const Constructable &c1) {
            return c0.getValue() != c1.getValue();
        }

        friend bool operator<(const Constructable &c0, const Constructable &c1) {
            return c0.getValue() < c1.getValue();
        }
        friend bool TURBO_ATTRIBUTE_UNUSED operator<=(const Constructable &c0,
                                                     const Constructable &c1) {
            return c0.getValue() <= c1.getValue();
        }
        friend bool TURBO_ATTRIBUTE_UNUSED operator>(const Constructable &c0,
                                                    const Constructable &c1) {
            return c0.getValue() > c1.getValue();
        }
        friend bool TURBO_ATTRIBUTE_UNUSED operator>=(const Constructable &c0,
                                                     const Constructable &c1) {
            return c0.getValue() >= c1.getValue();
        }
    };

    int Constructable::numConstructorCalls;
    int Constructable::numCopyConstructorCalls;
    int Constructable::numMoveConstructorCalls;
    int Constructable::numDestructorCalls;
    int Constructable::numAssignmentCalls;
    int Constructable::numCopyAssignmentCalls;
    int Constructable::numMoveAssignmentCalls;

    struct NonCopyable {
        NonCopyable() {}
        NonCopyable(NonCopyable &&) {}
        NonCopyable &operator=(NonCopyable &&) { return *this; }
    private:
        NonCopyable(const NonCopyable &) = delete;
        NonCopyable &operator=(const NonCopyable &) = delete;
    };

    TURBO_ATTRIBUTE_USED void CompileTest() {
        SmallVector<NonCopyable, 0> V;
        V.resize(42);
    }

    TEST(SmallVectorTest, ConstructNonCopyableTest) {
        SmallVector<NonCopyable, 0> V(42);
        EXPECT_EQ(V.size(), (size_t)42);
    }

// Assert that v contains the specified values, in order.
    template <typename VectorT>
    void assertValuesInOrder(VectorT &v, size_t size, ...) {
        EXPECT_EQ(size, v.size());

        va_list ap;
        va_start(ap, size);
        for (size_t i = 0; i < size; ++i) {
            int value = va_arg(ap, int);
            EXPECT_EQ(value, v[i].getValue());
        }

        va_end(ap);
    }

    template <typename VectorT> void assertEmpty(VectorT &v) {
        // Size tests
        EXPECT_EQ(0u, v.size());
        EXPECT_TRUE(v.empty());

        // Iterator tests
        EXPECT_TRUE(v.begin() == v.end());
    }

    // Generate a sequence of values to initialize the vector.
    template <typename VectorT> void makeSequence(VectorT &v, int start, int end) {
        for (int i = start; i <= end; ++i) {
            v.push_back(Constructable(i));
        }
    }

    template <typename T, unsigned N>
    constexpr static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
        return N;
    }

    class SmallVectorTestBase : public testing::Test {
    protected:
        void SetUp() override { Constructable::reset(); }
    };

// Test fixture class
    template <typename VectorT>
    class SmallVectorTest : public SmallVectorTestBase {
    protected:
        VectorT theVector;
        VectorT otherVector;
    };


    typedef ::testing::Types<SmallVector<Constructable, 0>,
    SmallVector<Constructable, 1>,
    SmallVector<Constructable, 2>,
    SmallVector<Constructable, 4>,
    SmallVector<Constructable, 5>
    > SmallVectorTestTypes;
    TYPED_TEST_SUITE(SmallVectorTest, SmallVectorTestTypes, );

// Constructor test.
    TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) {
        SCOPED_TRACE("ConstructorTest");
        auto &V = this->theVector;
        V = SmallVector<Constructable, 2>(2, 2);
        assertValuesInOrder(V, 2u, 2, 2);
    }

// Constructor test.
    TYPED_TEST(SmallVectorTest, ConstructorIterTest) {
        SCOPED_TRACE("ConstructorTest");
        int arr[] = {1, 2, 3};
        auto &V = this->theVector;
        V = SmallVector<Constructable, 4>(std::begin(arr), std::end(arr));
        assertValuesInOrder(V, 3u, 1, 2, 3);
    }

    // Constructor test.
    TYPED_TEST(SmallVectorTest, ConstructorFromArrayRefSimpleTest) {
        SCOPED_TRACE("ConstructorFromArrayRefSimpleTest");
        std::array<Constructable, 3> StdArray = {Constructable(1), Constructable(2),
                                                 Constructable(3)};
        ArrayRef<Constructable> Array = StdArray;
        auto &V = this->theVector;
        V = SmallVector<Constructable, 4>(Array);
        assertValuesInOrder(V, 3u, 1, 2, 3);
        ASSERT_EQ(NumBuiltinElts(TypeParam{}), NumBuiltinElts(V));
    }

// New vector test.
    TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
        SCOPED_TRACE("EmptyVectorTest");
        auto &V = this->theVector;
        assertEmpty(V);
        EXPECT_TRUE(V.rbegin() == V.rend());
        EXPECT_EQ(0, Constructable::getNumConstructorCalls());
        EXPECT_EQ(0, Constructable::getNumDestructorCalls());
    }

// Simple insertions and deletions.
    TYPED_TEST(SmallVectorTest, PushPopTest) {
        SCOPED_TRACE("PushPopTest");
        auto &V = this->theVector;
        // Track whether the vector will potentially have to grow.
        bool RequiresGrowth = V.capacity() < 3;

        // Push an element
        V.push_back(Constructable(1));

        // Size tests
        assertValuesInOrder(V, 1u, 1);
        EXPECT_FALSE(V.begin() == V.end());
        EXPECT_FALSE(V.empty());

        // Push another element
        V.push_back(Constructable(2));
        assertValuesInOrder(V, 2u, 1, 2);

        // Insert at beginning. Reserve space to avoid reference invalidation from
        // V[1].
        V.reserve(V.size() + 1);
        V.insert(V.begin(), V[1]);
        assertValuesInOrder(V, 3u, 2, 1, 2);

        // Pop one element
        V.pop_back();
        assertValuesInOrder(V, 2u, 2, 1);

        // Pop remaining elements
        V.pop_back_n(2);
        assertEmpty(V);

        // Check number of constructor calls. Should be 2 for each list element,
        // one for the argument to push_back, one for the argument to insert,
        // and one for the list element itself.
        if (!RequiresGrowth) {
            EXPECT_EQ(5, Constructable::getNumConstructorCalls());
            EXPECT_EQ(5, Constructable::getNumDestructorCalls());
        } else {
            // If we had to grow the vector, these only have a lower bound, but should
            // always be equal.
            EXPECT_LE(5, Constructable::getNumConstructorCalls());
            EXPECT_EQ(Constructable::getNumConstructorCalls(),
                      Constructable::getNumDestructorCalls());
        }
    }

// Clear test.
    TYPED_TEST(SmallVectorTest, ClearTest) {
        SCOPED_TRACE("ClearTest");
        auto &V = this->theVector;
        V.reserve(2);
        makeSequence(V, 1, 2);
        V.clear();

        assertEmpty(V);
        EXPECT_EQ(4, Constructable::getNumConstructorCalls());
        EXPECT_EQ(4, Constructable::getNumDestructorCalls());
    }

// Resize smaller test.
    TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
        SCOPED_TRACE("ResizeShrinkTest");
        auto &V = this->theVector;
        V.reserve(3);
        makeSequence(V, 1, 3);
        V.resize(1);

        assertValuesInOrder(V, 1u, 1);
        EXPECT_EQ(6, Constructable::getNumConstructorCalls());
        EXPECT_EQ(5, Constructable::getNumDestructorCalls());
    }

// Truncate test.
    TYPED_TEST(SmallVectorTest, TruncateTest) {
        SCOPED_TRACE("TruncateTest");
        auto &V = this->theVector;
        V.reserve(3);
        makeSequence(V, 1, 3);
        V.truncate(1);

        assertValuesInOrder(V, 1u, 1);
        EXPECT_EQ(6, Constructable::getNumConstructorCalls());
        EXPECT_EQ(5, Constructable::getNumDestructorCalls());

#if !defined(NDEBUG) && KTEST_HAS_DEATH_TEST
        EXPECT_DEATH(V.truncate(2), "Cannot increase size");
#endif
        V.truncate(1);
        assertValuesInOrder(V, 1u, 1);
        EXPECT_EQ(6, Constructable::getNumConstructorCalls());
        EXPECT_EQ(5, Constructable::getNumDestructorCalls());

        V.truncate(0);
        assertEmpty(V);
        EXPECT_EQ(6, Constructable::getNumConstructorCalls());
        EXPECT_EQ(6, Constructable::getNumDestructorCalls());
    }

// Resize bigger test.
    TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
        SCOPED_TRACE("ResizeGrowTest");
        auto &V = this->theVector;
        V.resize(2);

        EXPECT_EQ(2, Constructable::getNumConstructorCalls());
        EXPECT_EQ(0, Constructable::getNumDestructorCalls());
        EXPECT_EQ(2u, V.size());
    }

    TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) {
        auto &V = this->theVector;
        V.resize(2);

        Constructable::reset();

        V.resize(4);

        size_t Ctors = Constructable::getNumConstructorCalls();
        EXPECT_TRUE(Ctors == 2 || Ctors == 4);
        size_t MoveCtors = Constructable::getNumMoveConstructorCalls();
        EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);
        size_t Dtors = Constructable::getNumDestructorCalls();
        EXPECT_TRUE(Dtors == 0 || Dtors == 2);
    }

    // Resize with fill value.
    TYPED_TEST(SmallVectorTest, ResizeFillTest) {
        SCOPED_TRACE("ResizeFillTest");
        auto &V = this->theVector;
        V.resize(3, Constructable(77));
        assertValuesInOrder(V, 3u, 77, 77, 77);
    }

    TEST(SmallVectorTest, ResizeForOverwrite) {
        {
            // Heap allocated storage.
            SmallVector<unsigned, 0> V;
            V.push_back(5U);
            V.pop_back();
            V.resize_for_overwrite(V.size() + 1U);
            EXPECT_EQ(5U, V.back());
            V.pop_back();
            V.resize(V.size() + 1);
            EXPECT_EQ(0U, V.back());
        }
        {
            // Inline storage.
            SmallVector<unsigned, 2> V;
            V.push_back(5U);
            V.pop_back();
            V.resize_for_overwrite(V.size() + 1U);
            EXPECT_EQ(5U, V.back());
            V.pop_back();
            V.resize(V.size() + 1);
            EXPECT_EQ(0U, V.back());
        }
    }

// Overflow past fixed size.
    TYPED_TEST(SmallVectorTest, OverflowTest) {
        SCOPED_TRACE("OverflowTest");
        auto &V = this->theVector;
        // Push more elements than the fixed size.
        makeSequence(V, 1, 10);

        // Test size and values.
        EXPECT_EQ(10u, V.size());
        for (int i = 0; i < 10; ++i) {
            EXPECT_EQ(i + 1, V[i].getValue());
        }

        // Now resize back to fixed size.
        V.resize(1);

        assertValuesInOrder(V, 1u, 1);
    }

// Iteration tests.
    TYPED_TEST(SmallVectorTest, IterationTest) {
        auto &V = this->theVector;
        makeSequence(V, 1, 2);

        // Forward Iteration
        typename TypeParam::iterator it = V.begin();
        EXPECT_TRUE(*it == V.front());
        EXPECT_TRUE(*it == V[0]);
        EXPECT_EQ(1, it->getValue());
        ++it;
        EXPECT_TRUE(*it == V[1]);
        EXPECT_TRUE(*it == V.back());
        EXPECT_EQ(2, it->getValue());
        ++it;
        EXPECT_TRUE(it == V.end());
        --it;
        EXPECT_TRUE(*it == V[1]);
        EXPECT_EQ(2, it->getValue());
        --it;
        EXPECT_TRUE(*it == V[0]);
        EXPECT_EQ(1, it->getValue());

        // Reverse Iteration
        typename TypeParam::reverse_iterator rit = V.rbegin();
        EXPECT_TRUE(*rit == V[1]);
        EXPECT_EQ(2, rit->getValue());
        ++rit;
        EXPECT_TRUE(*rit == V[0]);
        EXPECT_EQ(1, rit->getValue());
        ++rit;
        EXPECT_TRUE(rit == V.rend());
        --rit;
        EXPECT_TRUE(*rit == V[0]);
        EXPECT_EQ(1, rit->getValue());
        --rit;
        EXPECT_TRUE(*rit == V[1]);
        EXPECT_EQ(2, rit->getValue());
    }

// Swap test.
    TYPED_TEST(SmallVectorTest, SwapTest) {
        SCOPED_TRACE("SwapTest");
        auto &V = this->theVector;
        auto &U = this->otherVector;
        makeSequence(V, 1, 2);
        std::swap(V, U);

        assertEmpty(V);
        assertValuesInOrder(U, 2u, 1, 2);
    }

// Append test
    TYPED_TEST(SmallVectorTest, AppendTest) {
        SCOPED_TRACE("AppendTest");
        auto &V = this->theVector;
        auto &U = this->otherVector;
        makeSequence(U, 2, 3);

        V.push_back(Constructable(1));
        V.append(U.begin(), U.end());

        assertValuesInOrder(V, 3u, 1, 2, 3);
    }

// Append repeated test
    TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
        SCOPED_TRACE("AppendRepeatedTest");
        auto &V = this->theVector;
        V.push_back(Constructable(1));
        V.append(2, Constructable(77));
        assertValuesInOrder(V, 3u, 1, 77, 77);
    }

// Append test
    TYPED_TEST(SmallVectorTest, AppendNonIterTest) {
        SCOPED_TRACE("AppendRepeatedTest");
        auto &V = this->theVector;
        V.push_back(Constructable(1));
        V.append(2, 7);
        assertValuesInOrder(V, 3u, 1, 7, 7);
    }

    struct output_iterator {
        typedef std::output_iterator_tag iterator_category;
        typedef int value_type;
        typedef int difference_type;
        typedef value_type *pointer;
        typedef value_type &reference;
        operator int() { return 2; }
        operator Constructable() { return 7; }
    };

    TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) {
        SCOPED_TRACE("AppendRepeatedTest");
        auto &V = this->theVector;
        V.push_back(Constructable(1));
        V.append(output_iterator(), output_iterator());
        assertValuesInOrder(V, 3u, 1, 7, 7);
    }

    TYPED_TEST(SmallVectorTest, AppendSmallVector) {
        SCOPED_TRACE("AppendSmallVector");
        auto &V = this->theVector;
        SmallVector<Constructable, 3> otherVector = {7, 7};
        V.push_back(Constructable(1));
        V.append(otherVector);
        assertValuesInOrder(V, 3u, 1, 7, 7);
    }

// Assign test
    TYPED_TEST(SmallVectorTest, AssignTest) {
        SCOPED_TRACE("AssignTest");
        auto &V = this->theVector;
        V.push_back(Constructable(1));
        V.assign(2, Constructable(77));
        assertValuesInOrder(V, 2u, 77, 77);
    }

// Assign test
    TYPED_TEST(SmallVectorTest, AssignRangeTest) {
        SCOPED_TRACE("AssignTest");
        auto &V = this->theVector;
        V.push_back(Constructable(1));
        int arr[] = {1, 2, 3};
        V.assign(std::begin(arr), std::end(arr));
        assertValuesInOrder(V, 3u, 1, 2, 3);
    }

// Assign test
    TYPED_TEST(SmallVectorTest, AssignNonIterTest) {
        SCOPED_TRACE("AssignTest");
        auto &V = this->theVector;
        V.push_back(Constructable(1));
        V.assign(2, 7);
        assertValuesInOrder(V, 2u, 7, 7);
    }

    TYPED_TEST(SmallVectorTest, AssignSmallVector) {
        SCOPED_TRACE("AssignSmallVector");
        auto &V = this->theVector;
        SmallVector<Constructable, 3> otherVector = {7, 7};
        V.push_back(Constructable(1));
        V.assign(otherVector);
        assertValuesInOrder(V, 2u, 7, 7);
    }

// Move-assign test
    TYPED_TEST(SmallVectorTest, MoveAssignTest) {
        SCOPED_TRACE("MoveAssignTest");
        auto &V = this->theVector;
        auto &U = this->otherVector;
        // Set up our vector with a single element, but enough capacity for 4.
        V.reserve(4);
        V.push_back(Constructable(1));

        // Set up the other vector with 2 elements.
        U.push_back(Constructable(2));
        U.push_back(Constructable(3));

        // Move-assign from the other vector.
        V = std::move(U);

        // Make sure we have the right result.
        assertValuesInOrder(V, 2u, 2, 3);

        // Make sure the # of constructor/destructor calls line up. There
        // are two live objects after clearing the other vector.
        U.clear();
        EXPECT_EQ(Constructable::getNumConstructorCalls()-2,
                  Constructable::getNumDestructorCalls());

        // There shouldn't be any live objects any more.
        V.clear();
        EXPECT_EQ(Constructable::getNumConstructorCalls(),
                  Constructable::getNumDestructorCalls());
    }

// Erase a single element
    TYPED_TEST(SmallVectorTest, EraseTest) {
        SCOPED_TRACE("EraseTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 3);
        const auto &theConstVector = V;
        V.erase(theConstVector.begin());
        assertValuesInOrder(V, 2u, 2, 3);
    }

// Erase a range of elements
    TYPED_TEST(SmallVectorTest, EraseRangeTest) {
        SCOPED_TRACE("EraseRangeTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 3);
        const auto &theConstVector = V;
        V.erase(theConstVector.begin(), theConstVector.begin() + 2);
        assertValuesInOrder(V, 1u, 3);
    }

// Insert a single element.
    TYPED_TEST(SmallVectorTest, InsertTest) {
        SCOPED_TRACE("InsertTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 3);
        typename TypeParam::iterator I = V.insert(V.begin() + 1, Constructable(77));
        EXPECT_EQ(V.begin() + 1, I);
        assertValuesInOrder(V, 4u, 1, 77, 2, 3);
    }

// Insert a copy of a single element.
    TYPED_TEST(SmallVectorTest, InsertCopy) {
        SCOPED_TRACE("InsertTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 3);
        Constructable C(77);
        typename TypeParam::iterator I = V.insert(V.begin() + 1, C);
        EXPECT_EQ(V.begin() + 1, I);
        assertValuesInOrder(V, 4u, 1, 77, 2, 3);
    }

// Insert repeated elements.
    TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
        SCOPED_TRACE("InsertRepeatedTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 4);
        Constructable::reset();
        auto I = V.insert(V.begin() + 1, 2, Constructable(16));
        // Move construct the top element into newly allocated space, and optionally
        // reallocate the whole buffer, move constructing into it.
        // FIXME: This is inefficient, we shouldn't move things into newly allocated
        // space, then move them up/around, there should only be 2 or 4 move
        // constructions here.
        EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
                    Constructable::getNumMoveConstructorCalls() == 6);
        // Move assign the next two to shift them up and make a gap.
        EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
        // Copy construct the two new elements from the parameter.
        EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
        // All without any copy construction.
        EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
        EXPECT_EQ(V.begin() + 1, I);
        assertValuesInOrder(V, 6u, 1, 16, 16, 2, 3, 4);
    }

    TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) {
        SCOPED_TRACE("InsertRepeatedTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 4);
        Constructable::reset();
        auto I = V.insert(V.begin() + 1, 2, 7);
        EXPECT_EQ(V.begin() + 1, I);
        assertValuesInOrder(V, 6u, 1, 7, 7, 2, 3, 4);
    }

    TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) {
        SCOPED_TRACE("InsertRepeatedTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 4);
        Constructable::reset();
        auto I = V.insert(V.end(), 2, Constructable(16));
        // Just copy construct them into newly allocated space
        EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
        // Move everything across if reallocation is needed.
        EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
                    Constructable::getNumMoveConstructorCalls() == 4);
        // Without ever moving or copying anything else.
        EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
        EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());

        EXPECT_EQ(V.begin() + 4, I);
        assertValuesInOrder(V, 6u, 1, 2, 3, 4, 16, 16);
    }

    TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) {
        SCOPED_TRACE("InsertRepeatedTest");
        auto &V = this->theVector;
        makeSequence(V, 10, 15);

        // Empty insert.
        EXPECT_EQ(V.end(), V.insert(V.end(), 0, Constructable(42)));
        EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, 0, Constructable(42)));
    }

// Insert range.
    TYPED_TEST(SmallVectorTest, InsertRangeTest) {
        SCOPED_TRACE("InsertRangeTest");
        auto &V = this->theVector;
        Constructable Arr[3] =
                { Constructable(77), Constructable(77), Constructable(77) };

        makeSequence(V, 1, 3);
        Constructable::reset();
        auto I = V.insert(V.begin() + 1, Arr, Arr + 3);
        // Move construct the top 3 elements into newly allocated space.
        // Possibly move the whole sequence into new space first.
        // FIXME: This is inefficient, we shouldn't move things into newly allocated
        // space, then move them up/around, there should only be 2 or 3 move
        // constructions here.
        EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
                    Constructable::getNumMoveConstructorCalls() == 5);
        // Copy assign the lower 2 new elements into existing space.
        EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
        // Copy construct the third element into newly allocated space.
        EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
        EXPECT_EQ(V.begin() + 1, I);
        assertValuesInOrder(V, 6u, 1, 77, 77, 77, 2, 3);
    }


    TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) {
        SCOPED_TRACE("InsertRangeTest");
        auto &V = this->theVector;
        Constructable Arr[3] =
                { Constructable(77), Constructable(77), Constructable(77) };

        makeSequence(V, 1, 3);

        // Insert at end.
        Constructable::reset();
        auto I = V.insert(V.end(), Arr, Arr + 3);
        // Copy construct the 3 elements into new space at the top.
        EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
        // Don't copy/move anything else.
        EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
        // Reallocation might occur, causing all elements to be moved into the new
        // buffer.
        EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
                    Constructable::getNumMoveConstructorCalls() == 3);
        EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
        EXPECT_EQ(V.begin() + 3, I);
        assertValuesInOrder(V, 6u, 1, 2, 3, 77, 77, 77);
    }

    TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) {
        SCOPED_TRACE("InsertRangeTest");
        auto &V = this->theVector;
        makeSequence(V, 1, 3);

        // Empty insert.
        EXPECT_EQ(V.end(), V.insert(V.end(), V.begin(), V.begin()));
        EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, V.begin(), V.begin()));
    }

// Comparison tests.
    TYPED_TEST(SmallVectorTest, ComparisonEqualityTest) {
        SCOPED_TRACE("ComparisonEqualityTest");
        auto &V = this->theVector;
        auto &U = this->otherVector;
        makeSequence(V, 1, 3);
        makeSequence(U, 1, 3);

        EXPECT_TRUE(V == U);
        EXPECT_FALSE(V != U);

        U.clear();
        makeSequence(U, 2, 4);

        EXPECT_FALSE(V == U);
        EXPECT_TRUE(V != U);
    }

// Comparison tests.
    TYPED_TEST(SmallVectorTest, ComparisonLessThanTest) {
        SCOPED_TRACE("ComparisonLessThanTest");
        auto &V = this->theVector;
        auto &U = this->otherVector;
        V = {1, 2, 4};
        U = {1, 4};

        EXPECT_TRUE(V < U);
        EXPECT_TRUE(V <= U);
        EXPECT_FALSE(V > U);
        EXPECT_FALSE(V >= U);

        EXPECT_FALSE(U < V);
        EXPECT_FALSE(U <= V);
        EXPECT_TRUE(U > V);
        EXPECT_TRUE(U >= V);

        U = {1, 2, 4};

        EXPECT_FALSE(V < U);
        EXPECT_TRUE(V <= U);
        EXPECT_FALSE(V > U);
        EXPECT_TRUE(V >= U);

        EXPECT_FALSE(U < V);
        EXPECT_TRUE(U <= V);
        EXPECT_FALSE(U > V);
        EXPECT_TRUE(U >= V);
    }

// Constant vector tests.
    TYPED_TEST(SmallVectorTest, ConstVectorTest) {
        const TypeParam constVector;

        EXPECT_EQ(0u, constVector.size());
        EXPECT_TRUE(constVector.empty());
        EXPECT_TRUE(constVector.begin() == constVector.end());
    }

// Direct array access.
    TYPED_TEST(SmallVectorTest, DirectVectorTest) {
        auto &V = this->theVector;
        EXPECT_EQ(0u, V.size());
        V.reserve(4);
        EXPECT_LE(4u, V.capacity());
        EXPECT_EQ(0, Constructable::getNumConstructorCalls());
        V.push_back(1);
        V.push_back(2);
        V.push_back(3);
        V.push_back(4);
        EXPECT_EQ(4u, V.size());
        EXPECT_EQ(8, Constructable::getNumConstructorCalls());
        EXPECT_EQ(1, V[0].getValue());
        EXPECT_EQ(2, V[1].getValue());
        EXPECT_EQ(3, V[2].getValue());
        EXPECT_EQ(4, V[3].getValue());
    }

    TYPED_TEST(SmallVectorTest, IteratorTest) {
        auto &V = this->theVector;
        std::list<int> L;
        V.insert(V.end(), L.begin(), L.end());
    }

    template <typename InvalidType> class DualSmallVectorsTest;

    template <typename VectorT1, typename VectorT2>
    class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase {
    protected:
        VectorT1 theVector;
        VectorT2 otherVector;
    };

    typedef ::testing::Types<
            // Small mode -> Small mode.
            std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>,
    // Small mode -> Big mode.
    std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>,
    // Big mode -> Small mode.
    std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>,
    // Big mode -> Big mode.
    std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>>
    > DualSmallVectorTestTypes;

    TYPED_TEST_SUITE(DualSmallVectorsTest, DualSmallVectorTestTypes, );

    TYPED_TEST(DualSmallVectorsTest, MoveAssignment) {
        SCOPED_TRACE("MoveAssignTest-DualVectorTypes");
        auto &V = this->theVector;
        auto &U = this->otherVector;
        // Set up our vector with four elements.
        for (unsigned I = 0; I < 4; ++I)
            U.push_back(Constructable(I));

        const Constructable *OrigDataPtr = U.data();

        // Move-assign from the other vector.
        V = std::move(static_cast<SmallVectorImpl<Constructable> &>(U));

        // Make sure we have the right result.
        assertValuesInOrder(V, 4u, 0, 1, 2, 3);

        // Make sure the # of constructor/destructor calls line up. There
        // are two live objects after clearing the other vector.
        U.clear();
        EXPECT_EQ(Constructable::getNumConstructorCalls()-4,
                  Constructable::getNumDestructorCalls());

        // If the source vector (otherVector) was in small-mode, assert that we just
        // moved the data pointer over.
        EXPECT_TRUE(NumBuiltinElts(U) == 4 || V.data() == OrigDataPtr);

        // There shouldn't be any live objects any more.
        V.clear();
        EXPECT_EQ(Constructable::getNumConstructorCalls(),
                  Constructable::getNumDestructorCalls());

        // We shouldn't have copied anything in this whole process.
        EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0);
    }

    struct notassignable {
        int &x;
        notassignable(int &x) : x(x) {}
    };

    TEST(SmallVectorCustomTest, NoAssignTest) {
        int x = 0;
        SmallVector<notassignable, 2> vec;
        vec.push_back(notassignable(x));
        x = 42;
        EXPECT_EQ(42, vec.pop_back_val().x);
    }

    struct MovedFrom {
        bool hasValue;
        MovedFrom() : hasValue(true) {
        }
        MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) {
            m.hasValue = false;
        }
        MovedFrom &operator=(MovedFrom&& m) {
            hasValue = m.hasValue;
            m.hasValue = false;
            return *this;
        }
    };

    TEST(SmallVectorTest, MidInsert) {
        SmallVector<MovedFrom, 3> v;
        v.push_back(MovedFrom());
        v.insert(v.begin(), MovedFrom());
        for (MovedFrom &m : v)
            EXPECT_TRUE(m.hasValue);
    }

    enum EmplaceableArgState {
        EAS_Defaulted,
        EAS_Arg,
        EAS_LValue,
        EAS_RValue,
        EAS_Failure
    };
    template <int I> struct EmplaceableArg {
        EmplaceableArgState State;
        EmplaceableArg() : State(EAS_Defaulted) {}
        EmplaceableArg(EmplaceableArg &&X)
                : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}
        EmplaceableArg(EmplaceableArg &X)
                : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}

        explicit EmplaceableArg(bool) : State(EAS_Arg) {}

    private:
        EmplaceableArg &operator=(EmplaceableArg &&) = delete;
        EmplaceableArg &operator=(const EmplaceableArg &) = delete;
    };

    enum EmplaceableState { ES_Emplaced, ES_Moved };
    struct Emplaceable {
        EmplaceableArg<0> A0;
        EmplaceableArg<1> A1;
        EmplaceableArg<2> A2;
        EmplaceableArg<3> A3;
        EmplaceableState State;

        Emplaceable() : State(ES_Emplaced) {}

        template <class A0Ty>
        explicit Emplaceable(A0Ty &&A0)
                : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}

        template <class A0Ty, class A1Ty>
        Emplaceable(A0Ty &&A0, A1Ty &&A1)
                : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
                  State(ES_Emplaced) {}

        template <class A0Ty, class A1Ty, class A2Ty>
        Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)
                : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
                  A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}

        template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>
        Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)
                : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
                  A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),
                  State(ES_Emplaced) {}

        Emplaceable(Emplaceable &&) : State(ES_Moved) {}
        Emplaceable &operator=(Emplaceable &&) {
            State = ES_Moved;
            return *this;
        }

    private:
        Emplaceable(const Emplaceable &) = delete;
        Emplaceable &operator=(const Emplaceable &) = delete;
    };

    TEST(SmallVectorTest, EmplaceBack) {
        EmplaceableArg<0> A0(true);
        EmplaceableArg<1> A1(true);
        EmplaceableArg<2> A2(true);
        EmplaceableArg<3> A3(true);
        {
            SmallVector<Emplaceable, 3> V;
            Emplaceable &back = V.emplace_back();
            EXPECT_TRUE(&back == &V.back());
            EXPECT_TRUE(V.size() == 1);
            EXPECT_TRUE(back.State == ES_Emplaced);
            EXPECT_TRUE(back.A0.State == EAS_Defaulted);
            EXPECT_TRUE(back.A1.State == EAS_Defaulted);
            EXPECT_TRUE(back.A2.State == EAS_Defaulted);
            EXPECT_TRUE(back.A3.State == EAS_Defaulted);
        }
        {
            SmallVector<Emplaceable, 3> V;
            Emplaceable &back = V.emplace_back(std::move(A0));
            EXPECT_TRUE(&back == &V.back());
            EXPECT_TRUE(V.size() == 1);
            EXPECT_TRUE(back.State == ES_Emplaced);
            EXPECT_TRUE(back.A0.State == EAS_RValue);
            EXPECT_TRUE(back.A1.State == EAS_Defaulted);
            EXPECT_TRUE(back.A2.State == EAS_Defaulted);
            EXPECT_TRUE(back.A3.State == EAS_Defaulted);
        }
        {
            SmallVector<Emplaceable, 3> V;
            Emplaceable &back = V.emplace_back(A0);
            EXPECT_TRUE(&back == &V.back());
            EXPECT_TRUE(V.size() == 1);
            EXPECT_TRUE(back.State == ES_Emplaced);
            EXPECT_TRUE(back.A0.State == EAS_LValue);
            EXPECT_TRUE(back.A1.State == EAS_Defaulted);
            EXPECT_TRUE(back.A2.State == EAS_Defaulted);
            EXPECT_TRUE(back.A3.State == EAS_Defaulted);
        }
        {
            SmallVector<Emplaceable, 3> V;
            Emplaceable &back = V.emplace_back(A0, A1);
            EXPECT_TRUE(&back == &V.back());
            EXPECT_TRUE(V.size() == 1);
            EXPECT_TRUE(back.State == ES_Emplaced);
            EXPECT_TRUE(back.A0.State == EAS_LValue);
            EXPECT_TRUE(back.A1.State == EAS_LValue);
            EXPECT_TRUE(back.A2.State == EAS_Defaulted);
            EXPECT_TRUE(back.A3.State == EAS_Defaulted);
        }
        {
            SmallVector<Emplaceable, 3> V;
            Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1));
            EXPECT_TRUE(&back == &V.back());
            EXPECT_TRUE(V.size() == 1);
            EXPECT_TRUE(back.State == ES_Emplaced);
            EXPECT_TRUE(back.A0.State == EAS_RValue);
            EXPECT_TRUE(back.A1.State == EAS_RValue);
            EXPECT_TRUE(back.A2.State == EAS_Defaulted);
            EXPECT_TRUE(back.A3.State == EAS_Defaulted);
        }
        {
            SmallVector<Emplaceable, 3> V;
            Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3);
            EXPECT_TRUE(&back == &V.back());
            EXPECT_TRUE(V.size() == 1);
            EXPECT_TRUE(back.State == ES_Emplaced);
            EXPECT_TRUE(back.A0.State == EAS_RValue);
            EXPECT_TRUE(back.A1.State == EAS_LValue);
            EXPECT_TRUE(back.A2.State == EAS_RValue);
            EXPECT_TRUE(back.A3.State == EAS_LValue);
        }
        {
            SmallVector<int, 1> V;
            V.emplace_back();
            V.emplace_back(42);
            EXPECT_EQ(2U, V.size());
            EXPECT_EQ(0, V[0]);
            EXPECT_EQ(42, V[1]);
        }
    }

    TEST(SmallVectorTest, DefaultInlinedElements) {
        SmallVector<int> V;
        EXPECT_TRUE(V.empty());
        V.push_back(7);
        EXPECT_EQ(V[0], 7);

        // Check that at least a couple layers of nested SmallVector<T>'s are allowed
        // by the default inline elements policy. This pattern happens in practice
        // with some frequency, and it seems fairly harmless even though each layer of
        // SmallVector's will grow the total sizeof by a vector header beyond the
        // "preferred" maximum sizeof.
        SmallVector<SmallVector<SmallVector<int>>> NestedV;
        NestedV.emplace_back().emplace_back().emplace_back(42);
        EXPECT_EQ(NestedV[0][0][0], 42);
    }

    TEST(SmallVectorTest, InitializerList) {
        SmallVector<int, 2> V1 = {};
        EXPECT_TRUE(V1.empty());
        V1 = {0, 0};
        EXPECT_TRUE(ArrayRef(V1).equals({0, 0}));
        V1 = {-1, -1};
        EXPECT_TRUE(ArrayRef(V1).equals({-1, -1}));

        SmallVector<int, 2> V2 = {1, 2, 3, 4};
        EXPECT_TRUE(ArrayRef(V2).equals({1, 2, 3, 4}));
        V2.assign({4});
        EXPECT_TRUE(ArrayRef(V2).equals({4}));
        V2.append({3, 2});
        EXPECT_TRUE(ArrayRef(V2).equals({4, 3, 2}));
        V2.insert(V2.begin() + 1, 5);
        EXPECT_TRUE(ArrayRef(V2).equals({4, 5, 3, 2}));
    }

    TEST(SmallVectorTest, ToVector) {
        {
            std::vector<char> v = {'a', 'b', 'c'};
            auto Vector = to_vector<4>(v);
            static_assert(NumBuiltinElts(Vector) == 4u);
            ASSERT_EQ(3u, Vector.size());
            for (size_t I = 0; I < v.size(); ++I)
                EXPECT_EQ(v[I], Vector[I]);
        }
        {
            std::vector<char> v = {'a', 'b', 'c'};
            auto Vector = to_vector(v);
            static_assert(NumBuiltinElts(Vector) != 4u);
            ASSERT_EQ(3u, Vector.size());
            for (size_t I = 0; I < v.size(); ++I)
                EXPECT_EQ(v[I], Vector[I]);
        }
    }

    struct To {
        int Content;
        friend bool operator==(const To &LHS, const To &RHS) {
            return LHS.Content == RHS.Content;
        }
    };

    class From {
    public:
        From() = default;
        From(To M) { T = M; }
        operator To() const { return T; }

    private:
        To T;
    };

    TEST(SmallVectorTest, ConstructFromArrayRefOfConvertibleType) {
        To to1{1}, to2{2}, to3{3};
        std::vector<From> StdVector = {From(to1), From(to2), From(to3)};
        ArrayRef<From> Array = StdVector;
        {
            turbo::SmallVector<To> Vector(Array);

            ASSERT_EQ(Array.size(), Vector.size());
            for (size_t I = 0; I < Array.size(); ++I)
                EXPECT_EQ(Array[I], Vector[I]);
        }
        {
            turbo::SmallVector<To, 4> Vector(Array);

            ASSERT_EQ(Array.size(), Vector.size());
            ASSERT_EQ(4u, NumBuiltinElts(Vector));
            for (size_t I = 0; I < Array.size(); ++I)
                EXPECT_EQ(Array[I], Vector[I]);
        }
    }

    TEST(SmallVectorTest, ToVectorOf) {
        To to1{1}, to2{2}, to3{3};
        std::vector<From> StdVector = {From(to1), From(to2), From(to3)};
        {
            turbo::SmallVector<To> Vector = turbo::to_vector_of<To>(StdVector);

            ASSERT_EQ(StdVector.size(), Vector.size());
            for (size_t I = 0; I < StdVector.size(); ++I)
                EXPECT_EQ(StdVector[I], Vector[I]);
        }
        {
            auto Vector = turbo::to_vector_of<To, 4>(StdVector);

            ASSERT_EQ(StdVector.size(), Vector.size());
            static_assert(NumBuiltinElts(Vector) == 4u);
            for (size_t I = 0; I < StdVector.size(); ++I)
                EXPECT_EQ(StdVector[I], Vector[I]);
        }
    }

    template <class VectorT>
    class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase {
    protected:
        const char *AssertionMessage =
                "Attempting to reference an element of the vector in an operation \" "
                "\"that invalidates it";

        VectorT V;

        template <class T> static bool isValueType() {
            return std::is_same_v<T, typename VectorT::value_type>;
        }

        void SetUp() override {
            SmallVectorTestBase::SetUp();

            // Fill up the small size so that insertions move the elements.
            for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
                V.emplace_back(I + 1);
        }
    };

    // Test one type that's trivially copyable (int) and one that isn't
    // (Constructable) since reference invalidation may be fixed differently for
    // each.
    using SmallVectorReferenceInvalidationTestTypes =
            ::testing::Types<SmallVector<int, 3>, SmallVector<Constructable, 3>>;

    TYPED_TEST_SUITE(SmallVectorReferenceInvalidationTest,
                     SmallVectorReferenceInvalidationTestTypes, );

    TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        int N = NumBuiltinElts(V);

        // Push back a reference to last element when growing from small storage.
        V.push_back(V.back());
        EXPECT_EQ(N, V.back());

        // Check that the old value is still there (not moved away).
        EXPECT_EQ(N, V[V.size() - 2]);

        // Fill storage again.
        V.back() = V.size();
        while (V.size() < V.capacity())
            V.push_back(V.size() + 1);

        // Push back a reference to last element when growing from large storage.
        V.push_back(V.back());
        EXPECT_EQ(int(V.size()) - 1, V.back());
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        int N = NumBuiltinElts(V);

        // Push back a reference to last element when growing from small storage.
        V.push_back(std::move(V.back()));
        EXPECT_EQ(N, V.back());
        if (this->template isValueType<Constructable>()) {
            // Check that the value was moved (not copied).
            EXPECT_EQ(0, V[V.size() - 2]);
        }

        // Fill storage again.
        V.back() = V.size();
        while (V.size() < V.capacity())
            V.push_back(V.size() + 1);

        // Push back a reference to last element when growing from large storage.
        V.push_back(std::move(V.back()));

        // Check the values.
        EXPECT_EQ(int(V.size()) - 1, V.back());
        if (this->template isValueType<Constructable>()) {
            // Check the value got moved out.
            EXPECT_EQ(0, V[V.size() - 2]);
        }
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) {
        auto &V = this->V;
        (void)V;
        int N = NumBuiltinElts(V);
        V.resize(N + 1, V.back());
        EXPECT_EQ(N, V.back());

        // Resize to add enough elements that V will grow again. If reference
        // invalidation breaks in the future, sanitizers should be able to catch a
        // use-after-free here.
        V.resize(V.capacity() + 1, V.front());
        EXPECT_EQ(1, V.back());
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, Append) {
        auto &V = this->V;
        (void)V;
        V.append(1, V.back());
        int N = NumBuiltinElts(V);
        EXPECT_EQ(N, V[N - 1]);

        // Append enough more elements that V will grow again. This tests growing
        // when already in large mode.
        //
        // If reference invalidation breaks in the future, sanitizers should be able
        // to catch a use-after-free here.
        V.append(V.capacity() - V.size() + 1, V.front());
        EXPECT_EQ(1, V.back());
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, AppendRange) {
        auto &V = this->V;
        (void)V;
#if !defined(NDEBUG) && KTEST_HAS_DEATH_TEST
        EXPECT_DEATH(V.append(V.begin(), V.begin() + 1), this->AssertionMessage);

        ASSERT_EQ(3u, NumBuiltinElts(V));
        ASSERT_EQ(3u, V.size());
        V.pop_back();
        ASSERT_EQ(2u, V.size());

        // Confirm this checks for growth when there's more than one element
        // appended.
        EXPECT_DEATH(V.append(V.begin(), V.end()), this->AssertionMessage);
#endif
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, Assign) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        (void)V;
        int N = NumBuiltinElts(V);
        ASSERT_EQ(unsigned(N), V.size());
        ASSERT_EQ(unsigned(N), V.capacity());

        // Check assign that shrinks in small mode.
        V.assign(1, V.back());
        EXPECT_EQ(1u, V.size());
        EXPECT_EQ(N, V[0]);

        // Check assign that grows within small mode.
        ASSERT_LT(V.size(), V.capacity());
        V.assign(V.capacity(), V.back());
        for (int I = 0, E = V.size(); I != E; ++I) {
            EXPECT_EQ(N, V[I]);

            // Reset to [1, 2, ...].
            V[I] = I + 1;
        }

        // Check assign that grows to large mode.
        ASSERT_EQ(2, V[1]);
        V.assign(V.capacity() + 1, V[1]);
        for (int I = 0, E = V.size(); I != E; ++I) {
            EXPECT_EQ(2, V[I]);

            // Reset to [1, 2, ...].
            V[I] = I + 1;
        }

        // Check assign that shrinks in large mode.
        V.assign(1, V[1]);
        EXPECT_EQ(2, V[0]);
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) {
        auto &V = this->V;
#if !defined(NDEBUG) && KTEST_HAS_DEATH_TEST
        EXPECT_DEATH(V.assign(V.begin(), V.end()), this->AssertionMessage);
        EXPECT_DEATH(V.assign(V.begin(), V.end() - 1), this->AssertionMessage);
#endif
        V.assign(V.begin(), V.begin());
        EXPECT_TRUE(V.empty());
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        (void)V;

        // Insert a reference to the back (not at end() or else insert delegates to
        // push_back()), growing out of small mode. Confirm the value was copied out
        // (moving out Constructable sets it to 0).
        V.insert(V.begin(), V.back());
        EXPECT_EQ(int(V.size() - 1), V.front());
        EXPECT_EQ(int(V.size() - 1), V.back());

        // Fill up the vector again.
        while (V.size() < V.capacity())
            V.push_back(V.size() + 1);

        // Grow again from large storage to large storage.
        V.insert(V.begin(), V.back());
        EXPECT_EQ(int(V.size() - 1), V.front());
        EXPECT_EQ(int(V.size() - 1), V.back());
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        (void)V;

        // Insert a reference to the back (not at end() or else insert delegates to
        // push_back()), growing out of small mode. Confirm the value was copied out
        // (moving out Constructable sets it to 0).
        V.insert(V.begin(), std::move(V.back()));
        EXPECT_EQ(int(V.size() - 1), V.front());
        if (this->template isValueType<Constructable>()) {
            // Check the value got moved out.
            EXPECT_EQ(0, V.back());
        }

        // Fill up the vector again.
        while (V.size() < V.capacity())
            V.push_back(V.size() + 1);

        // Grow again from large storage to large storage.
        V.insert(V.begin(), std::move(V.back()));
        EXPECT_EQ(int(V.size() - 1), V.front());
        if (this->template isValueType<Constructable>()) {
            // Check the value got moved out.
            EXPECT_EQ(0, V.back());
        }
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) {
        auto &V = this->V;
        (void)V;

        // Cover NumToInsert <= this->end() - I.
        V.insert(V.begin() + 1, 1, V.back());
        int N = NumBuiltinElts(V);
        EXPECT_EQ(N, V[1]);

        // Cover NumToInsert > this->end() - I, inserting enough elements that V will
        // also grow again; V.capacity() will be more elements than necessary but
        // it's a simple way to cover both conditions.
        //
        // If reference invalidation breaks in the future, sanitizers should be able
        // to catch a use-after-free here.
        V.insert(V.begin(), V.capacity(), V.front());
        EXPECT_EQ(1, V.front());
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertRange) {
        auto &V = this->V;
        (void)V;
#if !defined(NDEBUG) && KTEST_HAS_DEATH_TEST
        EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.begin() + 1),
                     this->AssertionMessage);

        ASSERT_EQ(3u, NumBuiltinElts(V));
        ASSERT_EQ(3u, V.size());
        V.pop_back();
        ASSERT_EQ(2u, V.size());

        // Confirm this checks for growth when there's more than one element
        // inserted.
        EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.end()), this->AssertionMessage);
#endif
    }

    TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBack) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        int N = NumBuiltinElts(V);

        // Push back a reference to last element when growing from small storage.
        V.emplace_back(V.back());
        EXPECT_EQ(N, V.back());

        // Check that the old value is still there (not moved away).
        EXPECT_EQ(N, V[V.size() - 2]);

        // Fill storage again.
        V.back() = V.size();
        while (V.size() < V.capacity())
            V.push_back(V.size() + 1);

        // Push back a reference to last element when growing from large storage.
        V.emplace_back(V.back());
        EXPECT_EQ(int(V.size()) - 1, V.back());
    }

    template <class VectorT>
    class SmallVectorInternalReferenceInvalidationTest
            : public SmallVectorTestBase {
    protected:
        const char *AssertionMessage =
                "Attempting to reference an element of the vector in an operation \" "
                "\"that invalidates it";

        VectorT V;

        void SetUp() override {
            SmallVectorTestBase::SetUp();

            // Fill up the small size so that insertions move the elements.
            for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
                V.emplace_back(I + 1, I + 1);
        }
    };

// Test pairs of the same types from SmallVectorReferenceInvalidationTestTypes.
    using SmallVectorInternalReferenceInvalidationTestTypes =
            ::testing::Types<SmallVector<std::pair<int, int>, 3>,
    SmallVector<std::pair<Constructable, Constructable>, 3>>;

    TYPED_TEST_SUITE(SmallVectorInternalReferenceInvalidationTest,
                     SmallVectorInternalReferenceInvalidationTestTypes, );

    TYPED_TEST(SmallVectorInternalReferenceInvalidationTest, EmplaceBack) {
        // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
        auto &V = this->V;
        int N = NumBuiltinElts(V);

        // Push back a reference to last element when growing from small storage.
        V.emplace_back(V.back().first, V.back().second);
        EXPECT_EQ(N, V.back().first);
        EXPECT_EQ(N, V.back().second);

        // Check that the old value is still there (not moved away).
        EXPECT_EQ(N, V[V.size() - 2].first);
        EXPECT_EQ(N, V[V.size() - 2].second);

        // Fill storage again.
        V.back().first = V.back().second = V.size();
        while (V.size() < V.capacity())
            V.emplace_back(V.size() + 1, V.size() + 1);

        // Push back a reference to last element when growing from large storage.
        V.emplace_back(V.back().first, V.back().second);
        EXPECT_EQ(int(V.size()) - 1, V.back().first);
        EXPECT_EQ(int(V.size()) - 1, V.back().second);
    }

} // end namespace
